fun main() {
    //未重叠： [Point(lng=104.514, lat=30.7787), Point(lng=104.53, lat=30.7776), Point(lng=104.529, lat=30.7621), Point(lng=104.512, lat=30.7621)]
    //重叠：  [Point(lng=104.514, lat=30.7787), Point(lng=104.53, lat=30.7776), Point(lng=104.529, lat=30.7621), Point(lng=104.52412, lat=30.78412)]
    val points = listOf(Point(1.0, 1.0), Point(3.0, 3.0), Point(3.0, 1.0), Point(1.0, 3.0))

    val res = isCross(points)

    println(res)
}

/**
 * 点
 */
data class Point(val lng: Double, val lat: Double)

/**
 * 线段
 */
data class Segment(val start: Point, val end: Point)

/**
 * 判断点的集合连接成的多边形是否相交
 */
fun isCross(points: List<Point>): Boolean {
    if (points.size <= 3) {
        return false
    }
    //定义线段，目前的多边形有多少条线段
    val segments = mutableListOf<Segment>()
    points.forEachIndexed { index, point ->
        if (index < points.size - 1) {
            segments.add(Segment(point, points[index + 1]))
        }
    }

    //判断线段是否相交
    for (i in 0 until segments.size - 2) {
        for (j in i + 2 until segments.size) {
            //求两条线段的交点
            val x1 = segments[i].start.lng
            val y1 = segments[i].start.lat
            val x2 = segments[i].end.lng
            val y2 = segments[i].end.lat

            val x3 = segments[j].start.lng
            val y3 = segments[j].start.lat
            val x4 = segments[j].end.lng
            val y4 = segments[j].end.lat

            val a1 = y2 - y1
            val b1 = x2 - x1
            val c1 = x1 * y2 - x2 * y1

            val a2 = y4 - y3
            val b2 = x4 - x3
            val c2 = x3 * y4 - x4 * y3

            val d = a1 * b2 - a2 * b1

            //交点
            val x = (b2 * c1 - b1 * c2) / d
            val y = (a2 * c1 - a1 * c2) / d

            //判断交点是否在线段内，在的话返回true
            if ((x in x1..x2 && y in y1..y2) || (x in x2..x1 && y in y2..y1)) {
                return true
            }
        }
    }
    return false
}